package com.atwulidun.sort;

import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {5, 4, 3, 2, 1};
        insertSort(arr);
    }

            public static void insertSort(int[] arr) {
        // 外层循环控制比较的轮数
        // 注意：这里是从第二个数开始！！！！
        for (int i = 1; i < arr.length; i++) {
            // 确定当前要插入到有序列表中的无序列表的值(即为当前无序列表中的第一个值)
            int insertValue = arr[i];
            // 确定要被插入的有序列表坐标的初始值(即为当前有序列表的最后一个值的坐标)
            int insertIndex = i - 1;
            // 下面用一个while循环将insertValue和有序列表中的值从右到左依次比较，
            // 若碰到一个比insertValue小的值，说明找到插入位置
            while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
                // 比如1 2 4 5，3 当3和5比较完后，3先暂时插到4和5之间，1 2 4 3 5，5的下标原本是4，现在变成了5
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            // 最极端的情况是insertValue < arr[0]，此时进入最后一次while循环后insertIndex == -1
            // 这里可以做个优化：如果有序列表的最后一个数比无序列表的第一个数都要小，那么下面的赋值语句就不用执行
            if (insertIndex + 1 != i) {
                arr[insertIndex + 1] = insertValue;
            }
            System.out.println("第" + i + "轮：");
            System.out.println(Arrays.toString(arr));
        }
        System.out.println("全部排序完后为：");
        System.out.println(Arrays.toString(arr));
    }
}
